package com.jack.leetcode.eachproblem_2020;

/**
 * Created by zhang_j on 2020/11/18
 */
public class 加油站 {

    public static void main(String[] args) {
        int[] gas = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(canCompleteCircuit(gas,cost));
        System.out.println(canCompleteCircuit1(gas,cost));
    }

    public static int canCompleteCircuit1(int[] gas, int[] cost){
        int n = gas.length;
        int spare = 0;
        int minSpace = Integer.MAX_VALUE;
        int min = 0;
        for(int i = 0;i < n;i++){
            spare += (gas[i] - cost[i]);
            if(spare < minSpace){
                minSpace = spare;
                min = i;
            }
        }
        return spare < 0 ? -1 : (min + 1) % n;
    }

    public static int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int result = -1;
        for(int i = 0;i < n;i++){
            if(gas[i] >= cost[i]){
                if(can(gas, cost, gas[i] - cost[i], i, (i + 1) % n)){
                    result = i;
                }
            }
        }
        return result;
    }
    private static boolean can(int[] gas, int[] cost, int tmp, int i, int index){
        if(index == i){
            return tmp >= 0;
        }
        if(tmp < 0){
            return false;
        }
        tmp = tmp + gas[index] - cost[index];
        return can(gas, cost, tmp, i, (index + 1) % gas.length);
    }
}
